package com.lihepeng.leecode.frequency.recursive;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 给出一组数字，返回该组数字的所有排列
 *
 */
public class Solution55 {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        List<Integer> outPut = new ArrayList<>();
        for (int i=0;i<num.length;i++) {
            outPut.add(num[i]);
        }

        backtrack(num.length,outPut,result,0);
        return result;
    }

    private void backtrack(int n ,List<Integer> outPut, ArrayList<ArrayList<Integer>> result,int first) {
        if (n == first) {
            // 结束
            result.add(new ArrayList<Integer>(outPut));
        }
        for (int i=first;i<n;i++) {
            Collections.swap(outPut,first,i);
            backtrack(n,outPut,result,first+1);
            Collections.swap(outPut,first,i);
        }
    }
    List<List<Integer>> result02 = new ArrayList<>();
    public List<List<Integer>> permute02(int[] num) {
        List<Integer> outPut = new ArrayList<>();
        boolean[]used = new boolean[num.length];
        backtrack(num,outPut,used);
        return result02;
    }

    /**
     * 站在一颗回溯树上需要考虑三个事情
     * 路径 ：已经做出的选择
     * 选择列表 ：可以做出那些选择
     * 结束条件 ：也就是到了决策树的最后面 没有办法做出选择
     *
     * @param num
     * @return
     */

    private void  backtrack(int []num,List<Integer> trace,boolean[]used){
        // 触发结束条件
        if (trace.size() == num.length) {
            // 结束
            result02.add(new ArrayList<>(trace));
            trace = new ArrayList<>();
        }
        for (int i=0;i<num.length;i++) {
            // 排除不合法的选择
            if (used[i]) {
                continue;
            }
            trace.add(num[i]);
            used[i] = true;
            backtrack(num,trace,used);
            // 取消选择
            trace.remove(trace.size()-1);
            used[i]= false;
        }

    }
}
